package SortAlgorithmPractice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BucketSort {
    public static void main(String[] args) {
        int[] arr = {3,1,5,6,9,7,8,10};
        System.out.printf("Sort before : %s\n", Arrays.toString(arr));
        bucketSort(arr);
        System.out.printf("Sort after : %s\n", Arrays.toString(arr));
    }

    public static void bucketSort(int[] arr){
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int bucketSize = 5;
        int bucketCount = (max - min)/bucketSize + 1;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        for(int num : arr){
            int index = (num - min)/bucketSize;
            buckets.get(index).add(num);
        }
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }
}
